package com.gitee.wsl.collections.deque.link
//
//
//import com.gitee.wsl.struct.deque.link.AccessOrderDeque.AccessOrder
//import com.gitee.wsl.struct.deque.link.LinkedDeque.PeekingIterator
//import com.github.benmanes.caffeine.cache.WriteOrderDeque.WriteOrder
//import com.github.benmanes.caffeine.testing.CollectionSubject.assertThat
//import com.google.common.truth.Truth.assertThat
//import org.testng.annotations.DataProvider
//import org.testng.annotations.Test
//import java.util.Collections
//import java.util.Deque
//import java.util.List
//import java.util.Objects
//import java.util.concurrent.ThreadLocalRandom
//
///**
// * A unit-test for the @[AbstractLinkedDeque] implementations.
// *
// * @author ben.manes@gmail.com (Ben Manes)
// */
//class LinkedDequeTest {
//    @Test(dataProvider = "empty")
//    fun clear_whenEmpty(deque: Deque<*>) {
//        deque.clear()
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "full")
//    fun clear_whenPopulated(deque: Deque<*>) {
//        deque.clear()
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun isEmpty_whenEmpty(deque: Deque<*>) {
//        assertThat(deque.isEmpty()).isTrue()
//    }
//
//    @Test(dataProvider = "full")
//    fun isEmpty_whenPopulated(deque: Deque<*>) {
//        assertThat(deque.isEmpty()).isFalse()
//    }
//
//    @Test(dataProvider = "empty")
//    fun size_whenEmpty(deque: Deque<*>) {
//        assertThat(deque.size).isEqualTo(0)
//    }
//
//    @Test(dataProvider = "full")
//    fun size_whenPopulated(deque: Deque<*>) {
//        assertThat(deque.size).isEqualTo(SIZE)
//    }
//
//    @Test(dataProvider = "empty")
//    fun contains_withNull(deque: Deque<*>) {
//        assertThat(deque.contains(null)).isFalse()
//    }
//
//    @Test(dataProvider = "full")
//    fun contains_whenFound(deque: LinkedDeque<LinkedValue?>) {
//        val index = ThreadLocalRandom.current().nextInt(deque.size)
//        assertThat(
//            deque.contains(
//                com.google.common.collect.Iterables.get<LinkedValue>(
//                    deque,
//                    index
//                )
//            )
//        ).isTrue()
//    }
//
//    @Test(dataProvider = "full")
//    fun contains_whenNotFound(deque: LinkedDeque<LinkedValue?>) {
//        val unlinked = LinkedValue(1)
//        assertThat(deque.contains(unlinked)).isFalse()
//    }
//
//    /* --------------- Move --------------- */
//    @Test(dataProvider = "full")
//    fun moveToFront_first(deque: LinkedDeque<LinkedValue?>) {
//        checkMoveToFront(deque, deque.getFirst())
//    }
//
//    @Test(dataProvider = "full")
//    fun moveToFront_middle(deque: LinkedDeque<LinkedValue?>) {
//        checkMoveToFront(
//            deque,
//            com.google.common.collect.Iterables.get<LinkedValue>(deque, SIZE / 2)
//        )
//    }
//
//    @Test(dataProvider = "full")
//    fun moveToFront_last(deque: LinkedDeque<LinkedValue?>) {
//        checkMoveToFront(deque, deque.getLast())
//    }
//
//    @Test(dataProvider = "full")
//    fun moveToBack_first(deque: LinkedDeque<LinkedValue?>) {
//        checkMoveToBack(deque, deque.getFirst())
//    }
//
//    @Test(dataProvider = "full")
//    fun moveToBack_middle(deque: LinkedDeque<LinkedValue?>) {
//        checkMoveToBack(
//            deque,
//            com.google.common.collect.Iterables.get<LinkedValue>(deque, SIZE / 2)
//        )
//    }
//
//    @Test(dataProvider = "full")
//    fun moveToBack_last(deque: LinkedDeque<LinkedValue?>) {
//        checkMoveToBack(deque, deque.getLast())
//    }
//
//    /* --------------- First / Last --------------- */
//    @Test(dataProvider = "empty")
//    fun isFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.isFirst(LinkedValue(0))).isFalse()
//        assertThat(deque.isFirst(null)).isFalse()
//    }
//
//    @Test(dataProvider = "full")
//    fun isFirst_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val first = Objects.requireNonNull(deque.first)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.isFirst(first)).isTrue()
//        assertThat(deque.contains(first)).isTrue()
//        assertThat(deque.first).isSameInstanceAs(first)
//    }
//
//    @Test(dataProvider = "empty")
//    fun isLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.isLast(LinkedValue(0))).isFalse()
//        assertThat(deque.isLast(null)).isFalse()
//    }
//
//    @Test(dataProvider = "full")
//    fun isLast_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val last = Objects.requireNonNull(deque.last)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.isLast(last)).isTrue()
//        assertThat(deque.contains(last)).isTrue()
//        assertThat(deque.last).isSameInstanceAs(last)
//    }
//
//    /* --------------- Peek --------------- */
//    @Test(dataProvider = "empty")
//    fun peek_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.peek()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun peek_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val first = Objects.requireNonNull(deque.first)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.contains(first)).isTrue()
//        assertThat(deque.first).isSameInstanceAs(first)
//        assertThat(deque.peek()).isSameInstanceAs(first)
//    }
//
//    @Test(dataProvider = "empty")
//    fun peekFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.peekFirst()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun peekFirst_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val first = Objects.requireNonNull(deque.first)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.contains(first)).isTrue()
//        assertThat(deque.first).isSameInstanceAs(first)
//        assertThat(deque.peekFirst()).isSameInstanceAs(first)
//    }
//
//    @Test(dataProvider = "empty")
//    fun peekLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.peekLast()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun peekLast_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val last = Objects.requireNonNull(deque.last)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.contains(last)).isTrue()
//        assertThat(deque.last).isSameInstanceAs(last)
//        assertThat(deque.peekLast()).isSameInstanceAs(last)
//    }
//
//    /* --------------- Get --------------- */
//    @Test(dataProvider = "empty")
//    fun getFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.getFirst() })
//    }
//
//    @Test(dataProvider = "full")
//    fun getFirst_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val first = Objects.requireNonNull(deque.first)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.contains(first)).isTrue()
//        assertThat(deque.first).isSameInstanceAs(first)
//        assertThat(deque.getFirst()).isSameInstanceAs(first)
//    }
//
//    @Test(dataProvider = "empty")
//    fun getLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.getLast() })
//    }
//
//    @Test(dataProvider = "full")
//    fun getLast_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val last = Objects.requireNonNull(deque.last)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.contains(last)).isTrue()
//        assertThat(deque.last).isSameInstanceAs(last)
//        assertThat(deque.getLast()).isSameInstanceAs(last)
//    }
//
//    /* --------------- Element --------------- */
//    @Test(dataProvider = "empty")
//    fun element_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.element() })
//    }
//
//    @Test(dataProvider = "full")
//    fun element_whenPopulated(deque: AbstractLinkedDeque<LinkedValue?>) {
//        val first = Objects.requireNonNull(deque.first)
//        assertThat(deque).hasSize(SIZE)
//        assertThat(deque.contains(first)).isTrue()
//        assertThat(deque.first).isSameInstanceAs(first)
//        assertThat(deque.element()).isSameInstanceAs(first)
//    }
//
//    /* --------------- Offer --------------- */
//    @Test(dataProvider = "empty")
//    fun offer_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        assertThat(deque.offer(value)).isTrue()
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun offer_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        assertThat(deque.offer(value)).isTrue()
//        assertThat(deque.peekFirst()).isNotSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun offer_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.offer(deque.peek())).isFalse()
//        assertThat(deque).hasSize(SIZE)
//    }
//
//    @Test(dataProvider = "empty")
//    fun offerFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        assertThat(deque.offerFirst(value)).isTrue()
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun offerFirst_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        assertThat(deque.offerFirst(value)).isTrue()
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isNotSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun offerFirst_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.offerFirst(deque.peek())).isFalse()
//        assertThat(deque).hasSize(SIZE)
//    }
//
//    @Test(dataProvider = "empty")
//    fun offerLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        assertThat(deque.offerLast(value)).isTrue()
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun offerLast_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        assertThat(deque.offerLast(value)).isTrue()
//        assertThat(deque.peekFirst()).isNotSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun offerLast_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.offerLast(deque.peek())).isFalse()
//        assertThat(deque).hasSize(SIZE)
//    }
//
//    /* --------------- Add --------------- */
//    @Test(dataProvider = "empty")
//    fun add_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        assertThat(deque.add(value)).isTrue()
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun add_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        assertThat(deque.add(value)).isTrue()
//        assertThat(deque.peekFirst()).isNotSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun add_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.add(deque.peek())).isFalse()
//    }
//
//    @Test(dataProvider = "empty")
//    fun addFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        deque.addFirst(value)
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun addFirst_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        deque.addFirst(value)
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isNotSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun addFirst_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<IllegalArgumentException>(
//            IllegalArgumentException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.addFirst(deque.peek()) })
//    }
//
//    @Test(dataProvider = "empty")
//    fun addLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        deque.addLast(value)
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun addLast_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        deque.addLast(value)
//        assertThat(deque.peekFirst()).isNotSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun addLast_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<IllegalArgumentException>(
//            IllegalArgumentException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.addLast(deque.peek()) })
//    }
//
//    @Test(dataProvider = "empty")
//    fun addAll_withEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.addAll(listOf<LinkedValue>())).isFalse()
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun addAll_withPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val expected = ArrayList<LinkedValue?>()
//        populate(expected)
//        assertThat(deque.addAll(expected)).isTrue()
//        assertThat(deque).containsExactlyElementsIn(expected).inOrder()
//    }
//
//    @Test(dataProvider = "full")
//    fun addAll_withSelf(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.addAll(deque)).isFalse()
//    }
//
//    /* --------------- Poll --------------- */
//    @Test(dataProvider = "empty")
//    fun poll_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.poll()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun poll_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peek()
//        assertThat(deque.poll()).isSameInstanceAs(first)
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun poll_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        var value: LinkedValue?
//        while ((deque.poll().also { value = it }) != null) {
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun pollFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.pollFirst()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun pollFirst_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.pollFirst()).isSameInstanceAs(first)
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun pollFirst_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        var value: LinkedValue?
//        while ((deque.pollFirst().also { value = it }) != null) {
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun pollLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.pollLast()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun pollLast_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val last = deque.peekLast()
//        assertThat(deque.pollLast()).isSameInstanceAs(last)
//        assertThat(deque.contains(last)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun pollLast_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        var value: LinkedValue?
//        while ((deque.pollLast().also { value = it }) != null) {
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    /* --------------- Remove --------------- */
//    @Test(dataProvider = "empty")
//    fun remove_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.remove() })
//    }
//
//    @Test(dataProvider = "full")
//    fun remove_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.remove()).isSameInstanceAs(first)
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun remove_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.remove()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun removeElement_notFound(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.remove(LinkedValue(0))).isFalse()
//    }
//
//    @Test(dataProvider = "full")
//    fun removeElement_whenFound(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.remove(first)).isTrue()
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun removeElement_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.peek()
//            assertThat(deque.remove(value)).isTrue()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun removeFirst_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.removeFirst() })
//    }
//
//    @Test(dataProvider = "full")
//    fun removeFirst_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.removeFirst()).isSameInstanceAs(first)
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun removeFirst_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.removeFirst()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun removeLast_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.removeLast() })
//    }
//
//    @Test(dataProvider = "full")
//    fun removeLast_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val last = deque.peekLast()
//        assertThat(deque.removeLast()).isSameInstanceAs(last)
//        assertThat(deque.contains(last)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun removeLast_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.removeLast()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun removeFirstOccurrence_notFound(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.removeFirstOccurrence(LinkedValue(0))).isFalse()
//    }
//
//    @Test(dataProvider = "full")
//    fun removeFirstOccurrence_whenFound(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.removeFirstOccurrence(first)).isTrue()
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun removeFirstOccurrence_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.peek()
//            assertThat(deque.removeFirstOccurrence(value)).isTrue()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun removeLastOccurrence_notFound(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.removeLastOccurrence(LinkedValue(0))).isFalse()
//    }
//
//    @Test(dataProvider = "full")
//    fun removeLastOccurrence_whenFound(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.removeLastOccurrence(first)).isTrue()
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun removeLastOccurrence_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.peek()
//            assertThat(deque.removeLastOccurrence(value)).isTrue()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "empty")
//    fun removeAll_withEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.removeAll(listOf<Any>())).isFalse()
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    @Test(dataProvider = "full")
//    fun remove_withPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.removeAll(List.of<LinkedValue?>(first))).isTrue()
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun removeAll_toEmpty(deque: LinkedDeque<LinkedValue>) {
//        assertThat(deque.removeAll(List.copyOf<LinkedValue>(deque))).isTrue()
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    /* --------------- Stack --------------- */
//    @Test(dataProvider = "empty")
//    fun push_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(1)
//        deque.push(value)
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isSameInstanceAs(value)
//        assertThat(deque).hasSize(1)
//    }
//
//    @Test(dataProvider = "full")
//    fun push_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val value = LinkedValue(SIZE)
//        deque.push(value)
//        assertThat(deque.peekFirst()).isSameInstanceAs(value)
//        assertThat(deque.peekLast()).isNotSameInstanceAs(value)
//        assertThat(deque).hasSize(SIZE + 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun push_whenLinked(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<IllegalArgumentException>(
//            IllegalArgumentException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.push(deque.peek()) })
//    }
//
//    @Test(dataProvider = "empty")
//    fun pop_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { deque.pop() })
//    }
//
//    @Test(dataProvider = "full")
//    fun pop_whenPopulated(deque: LinkedDeque<LinkedValue?>) {
//        val first = deque.peekFirst()
//        assertThat(deque.pop()).isSameInstanceAs(first)
//        assertThat(deque.contains(first)).isFalse()
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun pop_toEmpty(deque: LinkedDeque<LinkedValue?>) {
//        while (!deque.isEmpty()) {
//            val value = deque.pop()
//            assertThat(deque.contains(value)).isFalse()
//        }
//        assertThat(deque).isExhaustivelyEmpty()
//    }
//
//    /* --------------- Iterators --------------- */
//    @Test(dataProvider = "empty")
//    fun iterator_noMoreElements(deque: LinkedDeque<LinkedValue?>) {
//        val iterator: Iterator<LinkedValue?> = deque.iterator()
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { iterator.next() })
//    }
//
//    @Test(dataProvider = "empty")
//    fun iterator_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.iterator().hasNext()).isFalse()
//        assertThat(deque.iterator().peek()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun iterator_whenWarmed(deque: LinkedDeque<LinkedValue?>) {
//        val expected = ArrayList<LinkedValue?>()
//        populate(expected)
//
//        assertThat(deque.peek()).isNotNull()
//        assertThat(com.google.common.collect.Iterators.size(deque.iterator())).isEqualTo(deque.size)
//        assertThat(
//            com.google.common.collect.Iterators.elementsEqual(
//                deque.iterator(),
//                expected.iterator()
//            )
//        ).isTrue()
//    }
//
//    @Test(dataProvider = "full")
//    fun iterator_removal(deque: LinkedDeque<LinkedValue?>) {
//        val iterator = deque.iterator()
//        val value = iterator.next()
//        iterator.remove()
//
//        var remaining = 0
//        while (iterator.hasNext()) {
//            assertThat(iterator.next()).isNotSameInstanceAs(value)
//            remaining++
//        }
//        assertThat(remaining).isEqualTo(SIZE - 1)
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun iterator_removal_exception(deque: LinkedDeque<LinkedValue?>) {
//        val iterator = deque.iterator()
//        iterator.next()
//        iterator.remove()
//        org.junit.jupiter.api.Assertions.assertThrows<IllegalStateException>(
//            IllegalStateException::class.java,
//            org.junit.jupiter.api.function.Executable { iterator.remove() })
//    }
//
//    @Test(dataProvider = "empty")
//    fun descendingIterator_noMoreElements(deque: LinkedDeque<LinkedValue?>) {
//        val iterator: Iterator<LinkedValue?> = deque.descendingIterator()
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            org.junit.jupiter.api.function.Executable { iterator.next() })
//    }
//
//    @Test(dataProvider = "empty")
//    fun descendingIterator_whenEmpty(deque: LinkedDeque<LinkedValue?>) {
//        assertThat(deque.descendingIterator().hasNext()).isFalse()
//        assertThat(deque.descendingIterator().peek()).isNull()
//    }
//
//    @Test(dataProvider = "full")
//    fun descendingIterator_whenWarmed(deque: LinkedDeque<LinkedValue?>) {
//        val expected = ArrayList<LinkedValue?>()
//        populate(expected)
//        Collections.reverse(expected)
//
//        assertThat(deque.descendingIterator().peek()).isNotNull()
//        assertThat(
//            com.google.common.collect.Iterators.elementsEqual(
//                deque.descendingIterator(),
//                expected.iterator()
//            )
//        ).isTrue()
//    }
//
//    @Test(dataProvider = "full")
//    fun descendingIterator_removal(deque: LinkedDeque<LinkedValue?>) {
//        val iterator = deque.descendingIterator()
//        val value = iterator.next()
//        iterator.remove()
//
//        var remaining = 0
//        while (iterator.hasNext()) {
//            assertThat(iterator.next()).isNotEqualTo(value)
//            remaining++
//        }
//        assertThat(remaining).isEqualTo(SIZE - 1)
//        assertThat(deque).hasSize(SIZE - 1)
//    }
//
//    @Test(dataProvider = "full")
//    fun concat(deque: LinkedDeque<LinkedValue?>) {
//        val expect: com.google.common.collect.ImmutableList<LinkedValue> =
//            com.google.common.collect.ImmutableList.copyOf<LinkedValue>(
//                com.google.common.collect.Iterators.concat<LinkedValue>(
//                    deque.iterator(),
//                    deque.descendingIterator()
//                )
//            )
//        val actual =
//            Iterable<LinkedValue> {
//                PeekingIterator.concat(
//                    deque.iterator(), deque.descendingIterator()
//                )
//            }
//        assertThat(actual).containsExactlyElementsIn(expect).inOrder()
//    }
//
//    @Test(dataProvider = "full")
//    fun concat_peek(deque: LinkedDeque<LinkedValue?>) {
//        val iterator = PeekingIterator.concat(deque.iterator(), deque.iterator())
//        while (iterator.hasNext()) {
//            val expected: Unit = iterator.peek()
//            assertThat(iterator.next()).isEqualTo(expected)
//        }
//        assertThat(iterator.peek()).isNull()
//    }
//
//    @Test(dataProvider = "empty")
//    fun concat_noMoreElements(deque: LinkedDeque<LinkedValue?>) {
//        val iterator = PeekingIterator.concat(deque.iterator(), deque.iterator())
//        org.junit.jupiter.api.Assertions.assertThrows<NoSuchElementException>(
//            NoSuchElementException::class.java,
//            iterator::next
//        )
//    }
//
//    @Test(dataProvider = "full")
//    fun comparing(deque: LinkedDeque<LinkedValue?>) {
//        val expect: com.google.common.collect.ImmutableList<LinkedValue> =
//            com.google.common.collect.ImmutableList.copyOf<LinkedValue>(
//                com.google.common.collect.Iterators.concat<LinkedValue>(
//                    deque.iterator(),
//                    deque.descendingIterator()
//                )
//            )
//        val actual: Unit = PeekingIterator.comparing(
//            deque.iterator(), deque.descendingIterator(), comparator().reversed()
//        )
//        assertThat(actual.peek()).isEqualTo(expect.get(0))
//        assertThat(com.google.common.collect.ImmutableList.copyOf(actual)).containsExactlyElementsIn(
//            expect
//        ).inOrder()
//    }
//
//    @Test(dataProvider = "full")
//    fun comparing_uneven(deque: LinkedDeque<LinkedValue?>) {
//        val empty = AccessOrderDeque<LinkedValue>().iterator()
//        val left: Unit = PeekingIterator.comparing(deque.iterator(), empty, comparator().reversed())
//        val right: Unit =
//            PeekingIterator.comparing(empty, deque.iterator(), comparator().reversed())
//
//        assertThat(left.peek()).isEqualTo(deque.getFirst())
//        assertThat(right.peek()).isEqualTo(deque.getFirst())
//    }
//
//    /* --------------- Deque providers --------------- */
//    @DataProvider(name = "empty")
//    fun providesEmptyDeque(): Array<Array<Any>> {
//        return arrayOf<Array<Any>>(
//            arrayOf<Any>(AccessOrderDeque<LinkedValue>()),
//            arrayOf<Any>(WriteOrderDeque<LinkedValue>()),
//        )
//    }
//
//    @DataProvider(name = "full")
//    fun providesWarmedDeque(): Array<Array<Any>> {
//        val accessOrder = AccessOrderDeque<LinkedValue?>()
//        val writeOrder: WriteOrderDeque<LinkedValue?> = WriteOrderDeque<LinkedValue>()
//        populate(accessOrder)
//        populate(writeOrder)
//        return arrayOf(arrayOf(accessOrder), arrayOf(writeOrder))
//    }
//
//    fun populate(collection: MutableCollection<LinkedValue?>) {
//        for (i in 0..<SIZE) {
//            collection.add(LinkedValue(i))
//        }
//    }
//
//    class LinkedValue(val value: Int) : AccessOrder<LinkedValue?>,
//        WriteOrder<LinkedValue?> {
//        @get:Nullable
//        @get:Nullable
//        @Nullable
//        var previousInWriteOrder: LinkedValue? = null
//
//        @get:Nullable
//        @get:Nullable
//        @Nullable
//        var nextInWriteOrder: LinkedValue? = null
//
//        override fun equals(o: Any?): Boolean {
//            return (o is LinkedValue) && (value == o.value)
//        }
//
//        override fun hashCode(): Int {
//            return value
//        }
//
//        override fun toString(): String {
//            return com.google.common.base.MoreObjects.toStringHelper(this)
//                .add("value", value)
//                .add(
//                    "prev",
//                    if (previousInWriteOrder == null) null else previousInWriteOrder!!.value
//                )
//                .add("next", if (nextInWriteOrder == null) null else nextInWriteOrder!!.value)
//                .toString()
//        }
//    }
//
//    companion object {
//        const val SIZE: Int = 100
//
//        private fun checkMoveToFront(
//            deque: LinkedDeque<LinkedValue?>,
//            @Nullable element: LinkedValue?,
//        ) {
//            assertThat(element).isNotNull()
//            deque.moveToFront(element)
//            assertThat(deque).hasSize(SIZE)
//            assertThat(deque.peekFirst()).isEqualTo(element)
//        }
//
//        private fun checkMoveToBack(
//            deque: LinkedDeque<LinkedValue?>,
//            @Nullable element: LinkedValue?,
//        ) {
//            assertThat(element).isNotNull()
//            deque.moveToBack(element)
//            assertThat(deque).hasSize(SIZE)
//            assertThat(deque.getLast()).isEqualTo(element)
//        }
//
//        private fun comparator(): Comparator<LinkedValue> {
//            return Comparator.comparingInt { v: LinkedValue -> v.value }
//        }
//    }
//}
